 //987.二又树的垂序遍历
 //https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/?envType=daily-question&envId=2024-02-13
class Solution {
    // 列 行 值
    vector<pair<pair<int,int>,int>> nodes;
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        dfs(root,0,0);
        //按列排序
        sort(nodes.begin(),nodes.end());
        vector<vector<int>> ret;
        int lastcol = INT_MIN;
        for(const auto& [k,v]:nodes)
        {
            //如果当前列与上一个节点列相同 则归入一个数组
            if(lastcol != k.first)
            {
                lastcol = k.first;
                ret.push_back(vector<int>());
            }
            ret.back().push_back(v);
        }
        return ret;
    }

    //遍历树 依次取节点值
    void dfs(TreeNode* root,int row,int col)
    {
        if(root == nullptr) return;
        nodes.push_back({{col,row},root->val});
        dfs(root->left,row+1,col-1);
        dfs(root->right,row+1,col+1);
    }
};